#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>
#include<vector>
using namespace std;

void gulu_sort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;

	while (n > 0)
	{
		for (int i = 1; i < n; i++)
		{
			if (vv[i] < vv[i - 1])
			{
				swap(vv[i], vv[i - 1]);
			}
		}
		n--;
	}
}

void select_sort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;
	for (int i = 0; i < n; i++)
	{
		int minpos = i;
		for (int j = i; j < n; j++)
		{
			if (vv[minpos] > vv[j])
			{
				minpos = j;
			}
		}
		swap(vv[i], vv[minpos]);
	}
}

void insert_sort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;
	for (int i = 1; i < n; i++)
	{
		if (vv[i - 1] > vv[i])
		{
			int num = vv[i];
			int j = i - 1;
			while (j >= 0)
			{
				if (vv[j] > num)
				{
					vv[j + 1] = vv[j];
					j--;
				}
				else {
					break;
				}
			}
			vv[j + 1] = num;
		}
	}
}

void xier_sort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;

	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = gap; i < n; i++)
		{
			if (vv[i - gap] > vv[i])
			{
				int num = vv[i];
				int j = i - gap;
				while (j >= 0)
				{
					if (num < vv[j])
					{
						vv[j + gap] = vv[j];
						j -= gap;
					}
					else {
						break;
					}
				}
				vv[j + gap] = num;
			}
		}
	}
}
void adjustdown(vector<int>& vv, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && vv[child] < vv[child + 1])
		{
			child++;
		}
		if (child < n && vv[parent] < vv[child])
		{
			swap(vv[parent], vv[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

void heap_sort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		adjustdown(vv, n, i);
	}
	for (int i = n - 1; i > 0; i--)
	{
		swap(vv[0], vv[i]);
		adjustdown(vv, i, 0);
	}

}

void fast_sort(vector<int>& vv, int left, int right)
{
	if (left >= right) return;
	int begin = left, end = right;
	int flag = left;
	while (begin < end)
	{
		while (begin < end && vv[begin] < vv[flag])
		{
			begin++;
		}
		while (begin < end && vv[end] > vv[flag])
		{
			end--;
		}
		swap(vv[end], vv[begin]);
	}
	swap(vv[flag], vv[begin]);
	fast_sort(vv, left, begin);
	fast_sort(vv, begin + 1, right);
}

void _mergesort(vector<int>& vv, int left, int right, vector<int>& v)
{
	if (left >= right) return;
	int mid = (left + right) / 2;
	_mergesort(vv, left, mid, v);
	_mergesort(vv, mid + 1, right, v);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (vv[begin1] < vv[begin2])
		{
			v[i++] = vv[begin1++];
		}
		else {
			v[i++] = vv[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		v[i++] = vv[begin1++];
	}
	while (begin2 <= end2)
	{
		v[i++] = vv[begin2++];
	}
	for (int j = left; j <= right; j++)
	{
		vv[j] = v[j];
	}
}
void mergesort(vector<int>& vv)
{
	int n = vv.size();
	if (n < 2) return;
	vector<int> v(n);
	_mergesort(vv, 0, n - 1, v);
}
int main()
{
	vector<int> vv = { 33, 23, 1, 5, 3, 8, 45, 42 };

	//gulu_sort(vv);
	//select_sort(vv);
	//insert_sort(vv);
	//xier_sort(vv);
	//heap_sort(vv);
	//fast_sort(vv, 0, 7);
	mergesort(vv);
	for (auto& n : vv)
	{
		cout << n << ' ';
	}
	cout << endl;
	
	return 0;
}